package main

import "fmt"

//  1    2    3
// /  \  /      \
// 4    5        6
//                 \
//                   7

//         14  13
//         |   |
// 1   2   4   12
// \ /   / | \ /
//  3   5  8  9
//  \ / \     \
//   6   7     11

// given a tree
// 1. find nodes that have zero or 1 parent
// 2. write a function to tell if two nodes have common ancestor
// 3. find the farest ancestor

func findNodesWithZeroOrOneParent(edges [][2]int) []int {
	res := []int{}

	m := make(map[int][]int)
	set := make(map[int]bool)
	for _, edge := range edges {
		parent := edge[0]
		child := edge[1]
		set[parent] = true
		set[child] = true
		if _, ok := m[child]; ok == false {
			m[child] = []int{parent}
		} else {
			m[child] = append(m[child], parent)
		}
	}
	// fmt.Println(set)

	for id, _ := range set {
		if _, ok := m[id]; ok == false {
			// no ancestor
			res = append(res, id)
		} else {
			parents := m[id]
			if len(parents) > 1 {
				continue
			} else if _, ok := m[parents[0]]; ok == false {
				res = append(res, id)
			}
		}
	}
	return res
}
func hasCommonAncestor(edges [][2]int, x, y int) bool {

	m := make(map[int][]int)
	for _, edge := range edges {
		parent := edge[0]
		child := edge[1]
		if _, ok := m[child]; ok == false {
			m[child] = []int{parent}
		} else {
			m[child] = append(m[child], parent)
		}
	}

	queue := []int{x}
	ancestorsX := []int{}
	for len(queue) != 0 {
		temp := queue[0]
		queue = queue[1:] // pop()

		if _, ok := m[temp]; ok == true {
			for _, v := range m[temp] {
				ancestorsX = append(ancestorsX, v)
				queue = append(queue, v)
			}
		}
	}
	fmt.Println(ancestorsX)

	queue = []int{y}
	for len(queue) != 0 {
		temp := queue[0]
		if contains(ancestorsX, temp) {
			fmt.Println(ancestorsX)
			return true
		}
		queue = queue[1:] // pop()

		if _, ok := m[temp]; ok == true {
			for _, v := range m[temp] {
				// ancestorsX = append(ancestorsX, v)
				queue = append(queue, v)
			}
		}
	}
	return false
}

func contains(s []int, e int) bool {
	for _, a := range s {
		if a == e {
			return true
		}
	}
	return false
}

func farestAncestor(edges [][2]int, x int) []int {
	m := make(map[int][]int)
	for _, edge := range edges {
		parent := edge[0]
		child := edge[1]
		if _, ok := m[child]; ok == false {
			m[child] = []int{parent}
		} else {
			m[child] = append(m[child], parent)
		}
	}

	ancestors := []int{}
	queue := []int{x}
	for len(queue) != 0 {
		tempQ := []int{}
		for _, id := range queue {
			if _, ok := m[id]; ok == true {
				// has ancestors
				for _, v := range m[id] {
					tempQ = append(tempQ, v)
				}
			}
		}
		// fmt.Println(tempQ)
		ancestors = queue
		queue = tempQ
	}
	return ancestors
}

func main() {
	input1 := [][2]int{
		[2]int{1, 4}, [2]int{1, 5}, [2]int{2, 5}, [2]int{3, 6}, [2]int{6, 7},
	}

	input2 := [][2]int{
		{1, 3}, {2, 3}, {3, 6}, {5, 6}, {5, 7}, {4, 5}, {4, 8}, {4, 9}, {9, 11}, {14, 4}, {13, 12}, {12, 9},
	}
	fmt.Println(findNodesWithZeroOrOneParent(input1))

	fmt.Println(hasCommonAncestor(input2, 1, 3))

	fmt.Println(farestAncestor(input2, 9))
}
